package com.clps.algorithm.chapter14.最少回文分割;

public class demo01 {
    public static void main(String[] args) {

    }

    public int minCut(String s){
        int len = s.length();
        Boolean[][] isPal = new Boolean[len][len];
        for (int i = 0; i <len ; i++) {
            for (int j = 0; j <i ; j++) {
                char ch1 = s.charAt(i);
                char ch2 = s.charAt(j);
                if(ch1 == ch2 && (i<=j+1 || isPal[j+1][i-1])){
                    isPal[j][i] = true;
                }
            }
        }

        int[] dp = new int[len];
        for (int i = 0; i <len ; i++) {
            if(isPal[0][1]){
                dp[i] = 0;
            }else{
                dp[i] = i;
                for (int j = 0; j <=i ; j++) {
                    if(isPal[j][i]){
                        dp[i] = Math.min(dp[i],dp[j-1]+1);
                    }
                }
            }
        }
        return  dp[len-1];
    }
}
